package com.lw.leetcode.tree.c;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 1857. 有向图中最大颜色值
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/17 15:55
 */
public class LargestPathValue {

    public static void main(String[] args) {
        LargestPathValue test = new LargestPathValue();

        // 2
//        String str = "abdda";
//        int[][] arr = {{0, 1}, {2, 3}, {3, 4}};

        // 3
        String str = "abaca";
        int[][] arr = {{0, 1}, {0, 2}, {2, 3}, {3, 4}};

        int i = test.largestPathValue(str, arr);
        System.out.println(i);
    }

    public int largestPathValue(String colors, int[][] edges) {
        if (edges.length == 0) {
            return 1;
        }
        int length = colors.length();
        Map<Integer, Node> map = new HashMap<>();
        int[] arr = new int[length];
        char[] chars = colors.toCharArray();
        int[][] counts = new int[26][2];
        for (int[] edge : edges) {
            int a = edge[0];
            int b = edge[1];
            arr[b]++;
            Node an = map.computeIfAbsent(a, v -> new Node(a, chars[a] - 'a'));
            Node bn = map.computeIfAbsent(b, v -> new Node(b, chars[b] - 'a'));
            counts[chars[a] - 'a'][0]++;
            counts[chars[b] - 'a'][0]++;
            an.list.add(bn);
        }
        LinkedList<Integer> list = new LinkedList<>();
        int all = 0;
        for (int i = 0; i < length; i++) {
            if (arr[i] == 0) {
                list.add(i);
            } else {
                all++;
            }
        }
        List<Integer> items = new ArrayList<>(list);
        while (!list.isEmpty()) {
            Integer poll = list.poll();
            Node node = map.get(poll);
            if (node != null) {
                for (Node no : node.list) {
                    arr[no.v]--;
                    if (arr[no.v] == 0) {
                        list.add(no.v);
                        all--;
                    }
                }
            }
        }
        if (all != 0) {
            return -1;
        }
        int max = 0;
        for (int i = 0; i < 26; i++) {
            counts[i][1] = i;
        }
        Arrays.sort(counts, (a, b) -> Integer.compare(b[0], a[0]));
        for (int[] count : counts) {
            int i = count[1];
            if (count[0] <= max) {
                break;
            }
            for (Integer item : items) {
                max = Math.max(max, find(map.get(item), i));
            }
        }
        return max;
    }

    private int find(Node node, int c) {
        if (node == null) {
            return 0;
        }
        if (node.f == c + 1) {
            return node.m;
        }
        int max = 0;
        for (Node no : node.list) {
            max = Math.max(max, find(no, c));
        }
        if (node.c == c) {
            max++;
        }
        node.m = max;
        node.f = c + 1;
        return max;
    }

    private class Node {
        private int v;
        private int c;
        private List<Node> list = new ArrayList<>();
        private int f;
        private int m;

        public Node(int v, int c) {
            this.v = v;
            this.c = c;
        }
    }

}
